#ifndef MAZESOLVER_H
#define MAZESOLVER_H

class Maze;
class MazeCell;
class Coordinates;
class MazeCellCoordinated;

#include <vector>
#include <queue>
#include "LinePlotter.h"

/*
 * These are some default values for the maze cells
 */
const int VALUE_EMPTY = 0; // this is the value to denote if a value is empty, so if its a cell that has to filled in
const int VALUE_FILLED = -1; // this is the value for the walls or other inaccessible non-junction cells
const int VALUE_FILLED_JUNCTION = -2; // = valid result for neighborhood finder

// Some helper structures to return the path
typedef std::vector<Segment> Path;
typedef std::vector<Path> Paths;

/**
 * This helper class is used to represent the coordinates in the maze
 */
class Coordinates {
public:
	int  x, y, z;

	Coordinates(int x, int y, int z);

	// some functions to compare two coordinates
	bool operator==(const Coordinates& otherCoordinates) const;
	bool operator!=(const Coordinates& otherCoordinates) const;
	int operator[](const int index) const;
};

/**
 * This class is used to model a cell in the maze
 */
class MazeCell {
private:
	int value;
	unsigned char pixelValue;
public:
	MazeCell(unsigned char pixelValue = VALUE_EMPTY);

	void setValue(int value);
	int getValue();

	unsigned char getPixelValue();
};

/**
 * This class is used to keep a reference to a maze cell and its coordinates in the maze
 */
class MazeCellCoordinated {
public:
	MazeCell *cell;
	Coordinates coords;

	MazeCellCoordinated(MazeCell *cell, Coordinates &coords):
		cell(cell), coords(coords) {}
};


/**
 * This class is used to store partial solutions of alternative paths during the calculation of all paths
 */
class PartialSolution {
public:
	MazeCellCoordinated cc;
	Path res;
	
	PartialSolution(MazeCellCoordinated cc):
		cc(cc) {}
	PartialSolution(MazeCellCoordinated cc, Path res):
		cc(cc), res(res) {}
};

/**
 * This is the main class that represents the maze itself.
 */
class Maze {
private:
	MazeCell ***dataGrid; // the actual maze
	int xSize, ySize, zSize; // the sizes of the dimensions
public:
	Maze(const int x, const int y, const int z, unsigned char ***mazeGrid);
	~Maze();
	
	/**
	 * The solve method solves the maze and returns all valid paths
	 */
	Paths solve(Coordinates &entranceCoordinates, Coordinates &exitCoordinates);

	
	/**
	 * This method returns the cell that is located on the given coordinates in the maze
	 */
	MazeCell* getCell(Coordinates coordinates);

	/**
	 * The following methods are used to check or retrieve local information near a cell or in a corridor.
	 * They are used during the solve operation.
	 */

	/**
	 * This method returns all accessible neighbors of a cell.
	 */
	std::vector<MazeCellCoordinated> getNeighbors(MazeCellCoordinated&);
	
	/**
	 *  This method returns the last junction that was on its current floodfill, this is just used to determine what side of the corridor has to be filled when handling a loop.
	 */
	MazeCellCoordinated& getLastJunction(MazeCellCoordinated&);

	/**
	 * This checks if a maze cell is a junction
	 */
	bool isJunction(MazeCellCoordinated&);

	/**
	 * This method is used to resolve collisions in the rare case that we have to handle a loop.
	 */
	void resolveCollision(MazeCellCoordinated&, MazeCellCoordinated&);

	/**
	 * This method overwrites the corridor in the rare case we have to handle a loop.
	 */
	void overwriteCorridor(MazeCellCoordinated &previousCell, MazeCellCoordinated &currentCell, Coordinates &endCoordinates);

	/**
	 * This method checks if a successor of the current junction has a path to the entrance. This is used to check if an alternative path is valid.
	 */
	bool hasValidPath(Coordinates &previousCoordinates, MazeCellCoordinated &cc);
};

#endif MAZESOLVER_H